import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Sort {

    //插入排序
    /*
    时间复杂度O(N^2)
    空间复杂度O(1)
    稳定
     */
    public void insertsort(int[] arr)
    {
        for(int i=1;i< arr.length;i++)
        {
            int tmp=arr[i];
            int j=i-1;
            for(;j>=0;j--)
            {
                if(arr[j]>tmp)
                {
                    arr[j+1]=arr[j];
                }
                else
                {
                    arr[j+1]=tmp;
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    //希尔排序
    /*
    时间复杂度O(N^1.3)-O(N^1.5)
    空间复杂度O(1)
     */
    public void shellsort(int[] arr)
    {
                                         //23
        int gap= arr.length;            //12,23,56,45,78
        while(gap>1)
        {
            shell(arr,gap);
            gap=gap/2;//2
        }
        shell(arr,1);
    }
    public void shell(int[] arr,int gap)
    {
        for(int i=gap;i< arr.length;i++)//2  3
        {
            int tmp=arr[i];//23
            int j=i-gap;//1
            for(;j>=0;j=j-gap)
            {
                if(arr[j]>tmp)
                {
                    arr[j+gap]=arr[j];
                }
                else
                {
                    arr[j+gap]=tmp;
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }


    //选择排序
    /*
    时间复杂度O(N^2)
    空间复杂度O(1)
     */
    public void selectsort(int[] arr)
    {
        for (int i = 0; i < arr.length; i++) {
            int min=i;//最小值下标
            for(int j=i;j<arr.length;j++)
            {
                if(arr[j]<arr[min]) {
                    min = j;
                }
            }
            //与最小值交换
            int tmp=arr[i];
            arr[i]=arr[min];
            arr[min]=tmp;
        }
    }

    //选择排序
    /*
    时间复杂度O(N^2)
    空间复杂度O(1)
     */
    public void selectsort2(int[] arr)
    {
        int left=0;
        int right=arr.length-1;
        while(left<right)
        {
            int min=left;
            int max=left;
            for(int i=left+1;i<=right;i++)
            {
                if(arr[i]<arr[min])
                {
                    min=i;
                }
                if(arr[i]>arr[max])
                {
                    max=i;
                }
            }

            swap(arr,min,left);
            if(max==left)
            {
                max=min;
            }
            swap(arr,max,right);
            left++;
            right--;
        }
    }
    public void swap(int[] arr,int i ,int j)
    {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }


    /**
     * 堆排序：
     * 时间复杂度：O(N*logn)
     * 空间复杂度：O(1)
     */
    public  void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length-1;
        while (end > 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private  void createBigHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    private  void shiftDown(int[] array,int parent,int len) {
        int child = 2*parent+1;
        while (child < len) {
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    //冒泡排序
    /*
    时间复杂度：O(N^2)
   空间复杂度：O(1)
     */

    public void bubblesort(int[] arr)
    {
        for (int i = 0; i < arr.length; i++) {
            boolean flg=false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1])
                {
                    swap(arr,j,j+1);
                    flg=true;
                }

            }
            if(flg==false)
                return;
        }
    }

    //冒泡排序
    /*
    时间复杂度：O(N^2)
   空间复杂度：O(1)
     */
    public void bubblesort1(int[] arr)
    {
        for (int i = 0; i < arr.length; i++) {

            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1])
                {
                    swap(arr,j,j+1);

                }

            }
        }
    }


    //快速排序
    public void Quicksort(int[] arr)
    {
        Quick(arr,0,arr.length-1);
    }

    public void Quick(int[] arr,int start,int end)
    {
        if(start>=end)
        {
            return;
        }
        int prvid=partition(arr,start,end);
        Quick(arr,start,prvid-1);
        Quick(arr,prvid+1,end);

    }
    public int partition(int[] arr,int left,int right)
    {
        int tmp=arr[left];
        while(left<right)
        {
            while(left<right&&arr[right]>=tmp)
            {
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left]<=tmp)
            {
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=tmp;

        return left;
    }



    public int partition1(int[] arr,int left,int right)
    {
        int tmp=arr[left];
        int i=left;
        while(left<right)
        {
            while(left<right&&arr[right]>=tmp)
            {
                right--;
            }
            while(left<right&&arr[left]<=tmp)
            {
                left++;
            }
            int ret=arr[right];
            arr[right]=arr[left];
            arr[left]=ret;
        }
        swap(arr,left,i);
        arr[left]=tmp;

        return left;
    }

    //用非递归实现快速排序
     public void quicksort(int[] arr)
     {
         Deque<Integer> stack =new LinkedList<>();
         int left=0;
         int right=arr.length-1;
         int prvid=partition(arr,left,right);
         if(prvid>left+1)
         {
             stack.push(left);
             stack.push(prvid-1);
         }
         if(prvid<right-1)
         {
             stack.push(prvid+1);
             stack.push(right);
         }
         while(!stack.isEmpty())
         {
             right=stack.pop();
             left=stack.pop();
             prvid=partition(arr,left,right);
             if(prvid>left+1)
             {
                 stack.push(left);
                 stack.push(prvid-1);
             }
             if(prvid<right-1)
             {
                 stack.push(prvid+1);
                 stack.push(right);
             }
         }

     }


     //归并排序
    /**
     * 时间复杂度：N*logN
     * 空间复杂度：N
     * 稳定性：稳定的排序
     *       插入排序    冒泡排序  归并排序

     */
    public  void mergeSort(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    private  void mergeSortFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }

        int mid = (left+right) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private  void merge(int[] array,int start,int end,int mid) {
        int s1 = start;
        //int e1 = mid;
        int s2 = mid+1;
        //int e2 = end;
        int[] tmp = new int[end-start+1];
        int k = 0;//tmp数组的下标
        while (s1 <= mid && s2 <= end) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i+start] = tmp[i];
        }

    }
}
